`
https://leetcode.cn/problems/perfect-squares/
`

// 一次性计算出所有结果
const N = 10000
const dp = new Array(N + 1).fill(Infinity)
dp[0] = 0
for (let i = 1; i * i <= N; i++) {
  for (let j = i * i; j <= N; j++) {
    dp[j] = Math.min(dp[j], dp[j - i * i] + 1)
  }
}

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  return dp[n]
};

// test
console.log(numSquares(12)) // 3
console.log(numSquares(13)) // 2